﻿#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define MAX(a,b) (a>b?a:b)

struct Segment
{
	// 左
	int x1;
	// 右
	int x2;
};

static bool segmentComparator(const Segment& s1, const Segment& s2)
{
	return s1.x1 < s2.x1;
}

static int mostCountOfOverlappedSegments(vector<Segment>& vec)
{
	sort(vec.begin(), vec.end(), segmentComparator);
	priority_queue<int, vector<int>, greater<int>> smallHeap;
	int maxCount = 0;
	for (auto it = vec.begin(); it != vec.end(); it++)
	{
		smallHeap.push((*it).x2);
		while (!smallHeap.empty() && smallHeap.top() <= (*it).x1)
		{
			smallHeap.pop();
		}

		maxCount = MAX(maxCount, smallHeap.size());
	}

	return maxCount;
}

struct Rect
{
	// 左
	int x1;
	// 右
	int x2;
	// 底
	int y1;
	// 顶
	int y2;
};

static bool rectYComparator(const Rect& rect1, const Rect& rect2)
{
	return rect1.y1 < rect2.y1;
}

// 用于Rect.y2小根堆的比较器
struct RectY2Conparator
{
	bool operator()(Rect& a, Rect& b)
	{
		return a.y2 > b.y2;
	}
};

static int mostCountOfOverlappedRects_part(priority_queue<Rect, vector<Rect>, RectY2Conparator> heap)
{
	if (heap.size() == 1) return 1;

	vector<Rect> vec;
	while (!heap.empty())
	{
		vec.push_back(heap.top());
		heap.pop();
	}

	vector<Segment> segVec;
	for (auto it = vec.begin(); it != vec.end(); it++)
	{
		Segment s = { (*it).x1,(*it).x2 };
		segVec.push_back(s);
	}

	return mostCountOfOverlappedSegments(segVec);
}

static int mostCountOfOverlappedRects(vector<Rect>& vec)
{
	sort(vec.begin(), vec.end(), rectYComparator);

	int maxCount = 0;
	int curCount;

	priority_queue<Rect, vector<Rect>, RectY2Conparator> smallHeap;

	for (auto it = vec.begin(); it != vec.end(); it++)
	{
		if (!smallHeap.empty() && smallHeap.top().y2 <= (*it).y1)
		{
			curCount = mostCountOfOverlappedRects_part(smallHeap);
			maxCount = MAX(maxCount, curCount);
		}

		while (!smallHeap.empty() && smallHeap.top().y2 <= (*it).y1)
		{
			smallHeap.pop();
		}

		smallHeap.push(*it);
	}

	// 结算容器中剩余的矩形
	curCount = mostCountOfOverlappedRects_part(smallHeap);
	maxCount = MAX(maxCount, curCount);

	return maxCount;
}

static int mostCountOfOverlappedRects(const int* x1, const int* x2, const int* y1, const int* y2, const size_t rectCount)
{
	vector<Rect> vec;
	for (int i = 0; i < rectCount; i++)
	{
		Rect rect = { x1[i], x2[i], y1[i], y2[i] };
		vec.push_back(rect);
	}

	return mostCountOfOverlappedRects(vec);
}

/**
 * 平面内有n个矩形，第i个矩形的左下角坐标为(x1[i],y1[i]), 右上角坐标为(x2[i],y2[i]). 如果两个或者多个矩形有公共区域则认为它们是相互重叠的(不考虑边界和角落)。请计算出平面内重叠矩形数量最多的地方，有多少个矩形相互重叠。
 * 
 * 思路：
 * 一条直线上有很多不同起点、不同长度的线段，请计算出直线上线段重叠数量最多的地方，有多少条线段相互重叠?
 * 
 * |----------------------------------------------|
 * 0                                                
 * 
 * 1:  |-----------|
 *     1           4
 * 2:      |-----------|
 *         2           5
 * 3:          |---|
 *             3   4
 * 4:                  |---------|
 *                     5         7
 * 
 * 将所有的线段按照起点的大小从小到大排序，声明一个ordered_map，用于存放每条线段的终点。
 * step1：处理第1条线段，将线段1的终点4放入ordered_map，ordered_map:[4]。
 * step2：处理第2条线段，将线段2的终点4放入ordered_map，并将ordered_map中小于等于线段2起点2的数据都移除掉，但是目前ordered_map中没有这样的数据，故继续。ordered_map:[4,5]
 * step3：处理第3条线段，将线段3的终点4放入ordered_map，将ordered_map中小于等于线段3起点3的数据都移除掉，但是目前ordered_map中没有这样的数据，故继续。ordered_map:[4,4,5]
 * step4: 处理第4条线段, 将线段4的终点7放入ordered_map，并将ordered_map中小于等于线段4起点5的数据都移除掉. ordered_map:[7]
 * 
 * 由此可见，ordered_map中数据最多的时候是3条，故答案是3.
 * ordered_map的意义是，当重合区域以某条线段的起点开头的时候，最多盖几条线段。
 * 
 * 将这个思路推广到矩形重叠问题。
 * 将所有矩形按照底边的y值从小到大排序，声明一个容器，先将第一个矩形加入容器，第二个矩形出现，如果第一个矩形的顶高于该矩形的底，则加入容器，否则，结算容器，并将第一个矩形从容器中取出，依次这么处理剩余的所有矩形, 即每处理到一个矩形，要看一下容器中的矩形有没有顶小于等于当前矩形的底，有的话，先结算，后将顶小于等于当前矩形底的矩形从容器中移除。
 */
int main_mostOverlappedRectangles()
{
	int x1[] = {0,1,2,4,};
	int x2[] = {5,6,8,7,};
	int y1[] = {0,1,1,1,};
	int y2[] = {3,5,3,5,};
	auto count = sizeof(x1) / sizeof(int);

	int overlappedCount = mostCountOfOverlappedRects(x1, x2, y1, y2, count);
	printf("n=%d", overlappedCount);

	return 0;
}